#!/usr/bin/python
# Filename: Stack.py


class SStack:
    '''Sequential Stack with max length'''
    def __init__(self, max_length=20):
        self.items = [None] * max_length
        self.max_length = max_length
        self._top = -1

    def __str__(self):
        return str(self.items[:self._top+1])

    def pop(self):
        if self._top == -1:
            return None
        else:
            value = self.items[self._top]
            # this can be added for inner beauty
            # self.items[self.top] = None
            self._top -= 1
            return value

    def push(self, value):
        if self._top < self.max_length-1:
            self._top += 1
            self.items[self._top] = value
            return True
        else:
            return False

    def top(self):
        if self._top == -1:
            return None
        else:
            value = self.items[self._top]
            return value

    def clear(self):
        self._top = -1 # this is not inner beautiful
        
    def is_full(self):
        return self._top == self.max_length-1

    def is_empty(self):
        return self._top == -1


from LinkedList import Node


class Stack:

    def __init__(self):
        self.length = 0
        # _top is a reference, not a node,
        # and need not to be a node
        self._top = None

    def push(self, value):
        node = Node(value)
        node.next = self._top
        self._top = node
        self.length += 1

    def pop(self):
        if self.is_empty(): return None
        node = self._top
        value = node.value
        del node
        self._top = self._top.next
        self.length -= 1
        return value

    def top(self):
        if self.is_empty(): return None
        return self._top.value

    def clear(self):
        while self._top:
            node = self._top
            self._top.next
            del node

    def is_empty(self):
        return self._top == None

    def __str__(self):
        string = "current stack:\n-->\n"
        curr_node = self._top
        while curr_node:
            string += (str(curr_node) + '\n')
            curr_node = curr_node.next
        string += "=="
        return string


def eval_postfix(expr):
    import re
    token_list = re.split("([^0-9])", expr)
    print token_list
    stack = Stack()
    for token in token_list:
        if token == '' or token == ' ':
            continue
        if token in ('+', '-', '*', '/'):
            b = str(stack.pop())
            a = str(stack.pop())
            e = a + token + b
            stack.push(eval(e))
            print stack
        else:
            try:
                c = int(token)
            except:
                pass
            else:
                stack.push(c)
                print stack
    return stack.pop()

def match_parenthesis(expr, end='#'):
    import re
    token_list = re.split("([^0-9])", expr)
    print token_list
    # end mark test
    if expr.count(end) != 1 or expr[-1] != end:
        print "end mark test failed"
        return False
    stack = Stack()
    stack.push(end)
    for token in token_list:
        if token == '(':
            stack.push(token)
        elif token == ')':
            if stack.pop() != '(':
                return False
        elif token == end:
            if stack.pop() != token:
                return False
            else:
                return True
        else:
            pass

def infix_to_postfix(expr, end='#'):
    import re
    in_list = re.split("([^0-9])", expr)
    print in_list
    #end mark test
    if expr.count(end) != 1 or expr[-1] != end:
        print "end mark test failed"
        return None
    stack = Stack()
    post_list = []
    for token in in_list:
        if token == '' or token == ' ':
            continue
        elif token in ('+', '-', '*', '/', '(', ')'):
            if token == '(':
                stack.push('(')
            elif token == ')':
                while (not stack.is_empty()) and (not stack.top() == '('):
                    post_list.append(stack.pop())
                if stack.top() == '(':
                    stack.pop()
                else: # stack is empty
                    print "parenthesis is not match"
                    stack.clear()
                    return None
            else:
                if stack.is_empty() or stack.top() == '(': stack.push(token)
                else:
                    if (token == '*' or token == '/'):
                        while (stack.top() == '*' or stack.top() == '/'):
                            post_list.append(stack.pop())
                    else:
                        while (stack.top() in ('+', '-', '*', '/')):
                            post_list.append(stack.pop())
                    stack.push(token)
        elif token == '#':
            while not stack.is_empty(): post_list.append(stack.pop())
        else:
            try:
                num = int(token)
            except:
                print "invalid character"
                stack.clear()
                return None
            else:
                post_list.append(num)
    return post_list
            

if __name__ == "__main__":
    # (56+47)*2-4
    print eval_postfix("56, 47, +, 2, *, 4, -, ")

    print "3+3+4+5:", match_parenthesis("3+3+4+5#")
    print "3+(3+4+5):", match_parenthesis("3+(3+4+5)#")
    print "3+(3+4+5:", match_parenthesis("3+(3+4+5#")
    print "3+)3+(4+5)(:", match_parenthesis("3+)3+(4+5)(#")
    print "3+#3+(4+5):", match_parenthesis("3+#3+(4+5)")

    print infix_to_postfix("56+47*2-4/6#")
    print infix_to_postfix("(56+47)*(2-4)/6#")
    print infix_to_postfix("56+47+2-4-6#")
    print infix_to_postfix("56#+47+2-4-6#")
    print infix_to_postfix("56z+47+2-4-6#")

    print "factorial test of stack"
    # using stack to solve recursive
    # here's always a recursive machine: F(n) = nF'(n-1)
    # we push n into stack until F' has a instant value.
    # to mark the instant value as different is very important,
    # and list is used here to mark that,
    # or else it hard to distinguash
    def factorial(n):
        '''n > 0 and n is integer'''
        stack = Stack()
        stack.push(n)
        while not stack.is_empty():
            t = stack.pop()
            if type(t) == type([1]):
                if stack.is_empty():
                    return t[0]
                else:
                    t[0] *= stack.pop()
                    stack.push(t)
            else:
                if t == 1:
                    stack.push([1])
                else:
                    stack.push(t)
                    stack.push(t-1)

    print "factorial(5):", factorial(5)
    print "factorial(1):", factorial(1)

    print "hanoi test of stack"
    # using stack to solve recursive
    def hanoi(n):
        '''n > 0 and n is integer'''
        h = [range(1, n+1), [], []]

        def move(a, b):
            '''move top of ath to bth'''
            print a, "->", b, ':',
            print h, "->",
            h[b].insert(0, h[a][0])
            del h[a][0]
            print h

        stack = Stack()
        stack.push((n, 0, 1, 2))
        while not stack.is_empty():
            t = stack.pop()
            if len(t) == 2:
                move(t[0], t[1])
            elif t[0] == 1:
                stack.push((t[1], t[3]))
            else:
                stack.push((t[0]-1, t[2], t[1], t[3]))
                stack.push((t[1], t[3]))
                stack.push((t[0]-1, t[1], t[3], t[2]))
                
    def hanoi3():
    # for hanoi(3, A, B, C):
    # h(2, A, C, B) -> h(1, A, B, C) -> move(A, C)/0
    #                  move(A, B)/1
    #                  h(1, C, A, B) -> move(C, B)/0,1
    # move(A, C)/2
    # h(2, B, A, C) -> h(1, B, C, A) -> move(B, A)/0
    #                  move(B, C)/1,2
    #                  h(1, A, B, C) -> move(A, C)/0,1,2
        pass

    def hanoi4():
    # for hanoi(4, A, B, C):
    # h(3, A, C, B) -> h(2, A, B, C) -> h(1, A, C, B) -> move(A, B)/0
    #                                   move(A, C)/1
    #                                   h(1, B, A, C) -> move(B, C)/0,1
    #                  move(A, B)/2
    #                  h(2, C, A, B) -> h(1, C, B, A) -> move(C, A)/0,3
    #                                   move(C, B)/1,2
    #                                   h(1, A, C, B) -> move(A, B)/0,1,2
    # move(A, C)/3
    # h(3, B, A, C) -> same as hanoi3()
        pass

    print "procedure of hanoi(4):"
    hanoi(4)
